package main

import "go-leetcode/leetcode/utils"

// 142. 环形链表 II
func main() {
	node1 := &utils.ListNode{Val: 3}
	node2 := &utils.ListNode{Val: 2}
	node3 := &utils.ListNode{Val: 0}
	node4 := &utils.ListNode{Val: -4}
	node1.Next = node2
	node2.Next = node3
	node3.Next = node4
	node4.Next = node2

	cycle := detectCycle(node1)

	println(cycle.Val)

}

func detectCycle(head *utils.ListNode) *utils.ListNode {
	// 假设有环， 入口到环的长度为a, 环的长度为c
	// 那快慢指针，假设快指针循环了n遍
	// slow 指针进入环后，又走了 b的距离与 fast 相遇。此时，fast 指针已经走完了环的 n 圈，
	// 那么可以得到两个等式，a + b =
	// 因此它走过的总距离为 a+n(b+c)+b=a+(n+1)b+nc
	if head == nil || head.Next == nil {
		return nil
	}

	slow, fast := head, head

	for fast != nil {
		slow = slow.Next
		fast = fast.Next
		if fast != nil {
			fast = fast.Next
		}

		if fast == nil {
			return nil
		}

		if fast == slow {
			p := head

			for p != slow {
				p = p.Next
				slow = slow.Next
			}

			return p
		}
	}

	return nil
}
